package FPGrowth;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class FPTree {
	// FP tree node
	public class FPTreeNode {
		private ItemPrefixSubtreeNode node = null;
		private LinkedList<FPTreeNode> childs = null;

		public FPTreeNode() {
			childs = new LinkedList<FPTreeNode>();
		}

		public FPTreeNode(ItemPrefixSubtreeNode newNode) {
			node = newNode;
			childs = new LinkedList<FPTreeNode>();
		}

		public void InsertTransaction(short[] dataArray, int minSupport) {
			SortItems(dataArray);
			FPTreeNode startNode = rootNode;
			InsertItems(dataArray, startNode, 0, minSupport);
		}

		public void InsertItems(short[] dataArray, FPTreeNode startNode,
				int indexList, int support) {
			boolean IsFound = false;
			int index = -1;
			for (int i = 0; i < startNode.childs.size(); i++) {
				if (dataArray[indexList] == startNode.childs.get(i).node.itemID) {
					IsFound = true;
					index = i;
					break;
				}
			}

			if (IsFound) {
				FPTreeNode t = startNode.childs.get(index);
				t.node.support++;
				startNode.childs.set(index, t);
				indexList++;
				if (indexList < dataArray.length
						&& supportCountHash.get(dataArray[indexList]) >= support) {
					InsertItems(dataArray, t, indexList, support);
				}
			} else {
				ItemPrefixSubtreeNode t = new ItemPrefixSubtreeNode(
						dataArray[indexList], 1, startNode.node);
				FPTreeNode insertNode = new FPTreeNode(t);
				startNode.childs.addLast(insertNode);

				// Link header Table and same value
				int indexHeader = findIndexHeaderTable(dataArray[indexList]);
				if (indexHeader != -1) {
					HeaderTable header = headerTable.get(indexHeader);
					// First item of type
					if (header.nodeLink == null) {
						header.nodeLink = insertNode.node;
						// headerTable.set(indexHeader, header);
					} else {
						ItemPrefixSubtreeNode ref = header.nodeLink;
						while (ref.refSameItem != null) {
							ref = ref.refSameItem;
						}
						ref.refSameItem = insertNode.node;
					}
				}

				indexList++;
				if (indexList < dataArray.length
						&& supportCountHash.get(dataArray[indexList]) >= support) {
					InsertItems(dataArray, insertNode, indexList, support);

				}
			}
		}
	}

	public static int findIndexHeaderTable(Short item) {
		for (int i = 0; i < headerTable.size(); i++) {
			if (headerTable.get(i).itemID == item)
				return i;
		}
		return -1;
	}

	public static void SortItems(short[] dataArray2) {
		boolean swapped = true;
		int j = 0;
		short tmp;
		while (swapped) {
			swapped = false;
			j++;
			for (int i = 0; i < dataArray2.length - j; i++) {
				if ((supportCountHash.get(dataArray2[i]) < supportCountHash
						.get(dataArray2[i + 1]))
						|| ((supportCountHash.get(dataArray2[i]) == supportCountHash
								.get(dataArray2[i + 1])) && (dataArray2[i] > dataArray2[i + 1]))) {
					tmp = dataArray2[i];
					dataArray2[i] = dataArray2[i + 1];
					dataArray2[i + 1] = tmp;
					swapped = true;
				}
			}
		}
	}

	// header table
	public class HeaderTable {
		protected short itemID;
		private int supportCount;
		private ItemPrefixSubtreeNode nodeLink = null;

		public HeaderTable(short colNum, int support) {
			supportCount = support;
			itemID = colNum;
		}
	}

	public static void CompleteHeaderTable() {
		boolean swapped = true;
		int j = 0;
		HeaderTable tmp;
		// Update support
		for (int i = 0; i < headerTable.size(); i++) {
			tmp = headerTable.get(i);
			tmp.supportCount = supportCountHash.get(tmp.itemID);
			headerTable.set(i, tmp);
		}
		// sort
		while (swapped) {
			swapped = false;
			j++;
			for (int i = 0; i < headerTable.size() - j; i++) {
				if (headerTable.get(i).supportCount < headerTable.get(i + 1).supportCount) {
					tmp = headerTable.get(i);
					headerTable.set(i, headerTable.get(i + 1));
					headerTable.set(i + 1, tmp);
					swapped = true;
				}
			}
		}
	}

	// Item prefix subtree node
	public class ItemPrefixSubtreeNode {
		protected short itemID;
		private int support;
		private ItemPrefixSubtreeNode parent = null;
		private ItemPrefixSubtreeNode refSameItem = null;

		public ItemPrefixSubtreeNode() {

		}

		public ItemPrefixSubtreeNode(short name, int itemCount,
				ItemPrefixSubtreeNode backRef) {
			itemID = name;
			support = itemCount;
			parent = backRef;
			// refSameItem = new ItemPrefixSubtreeNode();
		}
	}

	// update support hash
	public void updateSupportCountHash(short item) {
		if (supportCountHash.containsKey(item)) {
			supportCountHash.put(item, supportCountHash.get(item) + 1);
		} else {
			supportCountHash.put(item, 1);
			// Add items to headerTable
			HeaderTable itemType = new HeaderTable(item, 0);
			headerTable.addLast(itemType);
		}

	}

	// get total rows in file
	public int getRows(String fileName) {
		int numRows = 0;
		File file = new File(fileName);
		BufferedReader reader = null;
		
		try {
			reader = new BufferedReader(new FileReader(file));
			String line = reader.readLine();
			while (line != null) {
				numRows++;
				line = reader.readLine();
			}
			reader.close();
		} catch (Exception e) {
			
		}
		
		return numRows;
	}
	
	// read file to data array to reduce run time
	public void readFileToDataArray() {
		// read input from file
		File file = new File("input.txt");
		BufferedReader reader = null;
		int numRows = getRows("input.txt");
		dataArray = new short[numRows][];

		try {
			reader = new BufferedReader(new FileReader(file));
			int rowIndex = 0;
			String current;
			current = reader.readLine();		
			while (current != null) {			
				StringTokenizer line = new StringTokenizer(current);		
				dataArray[rowIndex] = new short[line.countTokens()];
				int colIndex = 0;
				while (line.hasMoreElements()) {
					dataArray[rowIndex][colIndex] = Short.parseShort(line.nextElement().toString());
					colIndex++;
				}
				rowIndex++;
				current = reader.readLine();
			}
			reader.close();		
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public FPTree() {
		rootNode = new FPTreeNode();
		headerTable = new LinkedList<HeaderTable>();
	}

	// fp tree root
	protected FPTreeNode rootNode;
	// header table
	protected static LinkedList<HeaderTable> headerTable = null;
	// support count hash
	protected static HashMap<Short, Integer> supportCountHash = new HashMap<>();
	// data array to store input data read from file
	protected static short[][] dataArray = null;

	
	public static void main(String[] args) {
		FPTree programe = new FPTree();

		long start = System.currentTimeMillis();

		/*
		// read input from file
		File file = new File("input.txt");
		BufferedReader reader = null;
		Scanner input = null;

		// compute support for each item
		try {
			reader = new BufferedReader(new FileReader(file));
		} catch (FileNotFoundException e1) {
			e1.printStackTrace();
		}

		try {
			String current;
			current = reader.readLine();
			while (current != null) {
				input = new Scanner(current);
				
				while (input.hasNext()) {
					programe.updateSupportCountHash(input.nextShort());
				}
				current = reader.readLine();
			}
			reader = null;
			input = null;
		} catch (IOException e) {
			e.printStackTrace();
		}
		*/

		programe.readFileToDataArray();
		
		for(int i = 0; i < dataArray.length; i++) {
			for(int j = 0; j < dataArray[i].length; j++) {
				programe.updateSupportCountHash(dataArray[i][j]);
			}
		}
		
		long end = System.currentTimeMillis();

		System.out.println("time of read file: " + (long) ((end - start)));
		
		/*start = System.currentTimeMillis(); 
		CompleteHeaderTable(); 
		end = System.currentTimeMillis(); 
		System.out.println("time of calculate: "+
				 (long)((end - start)));*/
		
		// add node to fp tree
		start = System.currentTimeMillis();
		
		for(int i = 0; i < dataArray.length; i++) {
			programe.rootNode.InsertTransaction(dataArray[i], 0);
		}
		
		end = System.currentTimeMillis();
		System.out.println("time of fp generate: " + (long) ((end - start)));

	}
}
